\chapter{Semantic Association Ranking}

In the previous chapter, discussed a way of combining the full text search and ontology search. In this chapter, focus is on the methods of ranking relationship between two entities, i.e, given the two concepts need to find the best relationship path sequence between them. 

\section{Semantic Associations}
\textit{Semantic Association} was  coined by Anyanwu. According to the definition two entities are semantically associated if they are connected or semantically similar. As ranking of documents is a main focus of todays search engines, ranking of relationships will be essential in tomorrows semantic search engines that would support discovery and mining of relationship in the Semantic Web. Semantic associations are classified into three types based on how they are connected.

\begin{enumerate}

\item{\textbf{P-Path Association(x,y)}}\\
	A directed path between instance or entity x and y exist in ontology. x and y are origin and terminus of the path respectively.

\begin{figure}[h]
\begin{center}
\fbox{\scalebox{0.8}{\includegraphics{ppath.pdf}}}
\end{center}
\caption{P-Path Association}
\label{fig:ppath}
\end{figure}

\textit{In figure ~\ref{fig:ppath}, Ram studied in IITB and IITB located in Mumbai. Here direction relathionship exist between Ram and Mumbai.}

\item{\textbf{P-Join Association(x,y)}}\\
	No direction relationship exist between resources x and y. But two paths emanated from x and y, have an intersection point or joint node.

\begin{figure}[h]
\begin{center}
\fbox{\scalebox{0.8}{\includegraphics{pjoin.pdf}}}
\end{center}
\caption{P-Join Association}
\label{fig:pjoin}
\end{figure}

\textit{In figure ~\ref{fig:pjoin}, Ram and Shyam have no direction relation, whereas they are connected by a common node Mumbai}

\item{\textbf{P-Iso Association(x,y)}}\\
	If two paths emanated from x and y, these paths are called isomorphism, If every couples of edges or nodes between two paths has semantic relationship.	 

\begin{figure}[h]
\begin{center}
\fbox{\scalebox{0.8}{\includegraphics{piso.pdf}}}
\end{center}
\caption{P-Iso Association}
\label{fig:piso}
\end{figure}

\textit{In figure ~\ref{fig:piso}, here even there is no direction connection exist between Picasa and Ravivarma but instances they have created two artifacts and exhibited in museums of same kind.}

\section{Context aware semantic association ranking}
Context aware semantic association ranking~\citep{aleman2003context} is ranking the path (relationship sequence) between two concepts in ontology based Context weight, user weights, subsumption weight and trust weight.

\begin{enumerate}

\item{\textbf{Context weight}}\\
Context is a region of ontology where the user is interested in. A region of interest is a subset of classes and properties of a schema. Weight is assigned to classes and properties which passes through the context. In class level paths that include instances of these class are assigned more score. In property level paths including the specified properties are given higher score. Subsequently  the relation that passes through these classes and properties will get more score and ranked higher in the result.
\begin{verbatim}
<region id="R1" weight=".65">
   <classLevel name="Monuments" includeSubclasses="all"/>
   <classLevel name="Museums" includeSubclasses="no"/>
   <propertyLevel name="locatedIn" domainRestrictions="Monuments"
       rangeRestrictions="India, Srilanka" />
</region>
\end{verbatim}

Context weight of path is calculated by
\begin{equation}
	C_p = \frac{1}{|C|} * \sum_{i=1}^{|regions|} * (r_i * (\sum c \in R_i)) (1 - \frac{|C \notin R|}{|C|} ) 
\end{equation}

Here,

$r_i$ is weight of region $R_i$,

$1-\frac{|C \notin R|}{|C|}$ part penalizes based portion of relationship component not in region.


\item{\textbf{Path length weight}}\\
User may be interested in most direct path because it infers a stronger relationship between entities. Alternatively user may wish to find possibly hidden, indirect paths, in this case longer paths needs to be given more weights. Path length is number of classes and properties appears in the path. 
\begin{figure}[h]
\begin{center}
\fbox{\scalebox{0.5}{\includegraphics{pathweight.pdf}}}
\end{center}
\caption{Path length weight}
\end{figure}
Path weight favours shortest is
\begin{equation}
	L_p	=	\frac{1}{|C|}
\end{equation}
Path weight favours longest is
\begin{equation}
	L_p	=	1 - \frac{1}{|C|}
\end{equation}

\item{\textbf{Subsumption weight}}\\
Entities in ontology, that are lower in the hierarchy have more specific meaning. We will assign more weight to them.

\begin{figure}[h]
\begin{center}
\fbox{\scalebox{0.5}{\includegraphics{subsumption.pdf}}}
\end{center}
\caption{Subsumption weight}
\end{figure}

Individual component weight is,
\begin{equation}
	C_i	=	\frac{H_{ci}}{H}
\end{equation}
	$H_{ci}$ is the position of the ith component in its hierarchy H (the class at the top has value 1).
Subsumption weight of the path is,
\begin{equation}
	S_p	=	\frac{1}{|C|} * \prod_{i=2}^{|C|+1} C_i
\end{equation}


\item{\textbf{Trust weight}}\\
Trust weight is to relations, it is like assigning weight to relations based on the source where it is obtained from.

Trust weight of path is 
\begin{equation}
T_p = \prod_{i=1}^{p \in C_p} t_pi
\end{equation}

\textbf{Overall rank of the path} is calculated using all the above weights


\begin{equation}
\boxed{W_p = k_1 * S_p + k_2 * L_p + k_3 * C_p + k_4 * T_p }
\end{equation}

\end{enumerate}
\end{enumerate}

\section{SemRank}
The previous part deals with context aware semantic association ranking based on context, path and subsumption weight. SemRank ~\citep{Anyanwu} makes use of information content measures on property and entity, refraction count and keymatch. ~\cite{Anyanwu} explains the methods for ranking p-Path associations.\\

\begin{enumerate}
\item{\textbf{Specificity}}\\
Consider X is discrete random variable with sample space [[P]]. P is set of all property types in a RDF description base. The probability that X=p is given by,
	\begin{equation}
		Pr(X=p) = \frac{|[[p]]^{\wedge}|}{|[[P]]^{\wedge}|}
	\end{equation}
	$|[[p]]^{\wedge}|$ is number of properties of p occurred in the RDF triplet.
	$|[[P]]^{\wedge}|$ is number of all properties occurred in the RDF triplet. 
Information content of the occurrence of property p, I(X=p) is
	\begin{equation}
		I_{s}(p) = I(X=p) = -log Pr(X=p)
	\end{equation}
	Specificity of property sequence (PS) is the maximum information contained in any property of sequence.
	\begin{equation}
		I_{s}(ps) = max_{vi} I_{s}(pi)
	\end{equation}
	\textit{
	Example:
	Number of occurrences of \textit{Purchased} = 20 
	Number of occurrences of all properties = 2000
	\begin{equation}
		Pr(X=purchased) = \frac{20}{ 2000 }	
	\end{equation}
	}

	
\item{\textbf{$\theta$ Specificity}}\\
$\theta$ represents the all the valid properties that may connect resources r1 and r2. The probability that X=$\theta$ is 
	\begin{equation}
		Pr(X \in \theta) = \frac{|[[\theta]]^{\wedge}|}{|[[P]]^{\wedge}|}
	\end{equation}
If X $\in \theta$ , then probability that X=p is 
	\begin{equation}
		Pr(X=p | X \in \theta) = \frac{|[[p]]^{\wedge}|}{|[[\theta]]^{\wedge}|}
	\end{equation}
Information content on property p, based on $\theta$ specificity
	\begin{equation}
		I_{\theta-s}(P) =  I(X=p | X \in \theta) = - log Pr(X=p | X \in \theta)
	\end{equation}	
$\theta$ specificity of property sequence ps
\begin{equation}
	I_{\theta-s}(ps) = min_{vi}{NI_{\theta-s}(p_i)}  + \frac{\sum_{vi}{NI_{\theta-s}(p_i)} - min_{vi}{NI_{\theta-s}(p_i)} }{n-1}
\end{equation}
It is not calculated as maximum theta-specificity of a property, because each value from different distributions. Normalized by length, so score wont be biased towards longer property sequence.

\item{\textbf{Refractions}}\\
Refractions denote discrepant structure of the result from possibilities that it gleaned from the schema. It refers to deviation from schema layer. Refractions often raise surprise, hence considered to be more informative.
\begin{equation}
	RC(PS) = \sum_{i=1}^{n-1} refraction(p_{i},p_{i+1})  \text{ for n $\geq$ 1}
\end{equation}
Example:\\
\textit{
Course101 [GradedBy] Jhon [EnrolsIn] Course398\\
Course101 [GradedBy] Jhon $=>$ Jhon as type of Teacher\\
Jhon [EnrolsIn] Course398 $=>$ Jhon as type of Student\\
Meaning of Jhon is different from first half, due to multiple inheritance of instances. 
Refractions considered to be more informative( Normally less expected).}

\item{\textbf{S-Match}}\\
A set of keywords given as preferences by user. For each property match is calculated with keyword.
\begin{equation}
SemMatch(k_i, p_j) = \frac{1}{2^d} 
\end{equation}
where d is minimum distance between property and keyword. More the distance, it will reduce score.
S-match for the path ps is
\begin{equation}
S-Match(ps) = \sum_i^n max_{j=1}^m { SemMatch(k_j, p_i) }
\end{equation}

\item{\textbf{SemRank}}\\
$\mu$ is the modulator, value of $\mu$ decides contribution of information content of an association to rank below,
\begin{equation}
I_{\mu}(ps) = (1-\mu) (I(ps))^{-1} +  (\mu) (I(ps))
\end{equation}
If $\mu$ is high, more informative relation will be ranked first.  Final ranking function for semantic association for the p-Path association is
\begin{equation}
\boxed{
SEMRANK(SA) = I_{\mu}(ps) * (1+RC_{\mu}(ps)) * (1+S-Match(ps)) 
}
\end{equation}
\end{enumerate}

\section*{Summary}
In this chapter, We started our discussion with identifying kinds of association exist between concepts. Next we presented two methods of ranking relationships: \textit{(i) context aware semantic ranking, (ii) semRank: which is based in the information content measure on relationship sequnce.} 

In the next chapter, We conclude our present work with the work we want to do in future. 